//package work.rightAnswer;
//
//import java.util.ArrayList;
//import java.util.HashMap;
//import java.util.List;
//import java.util.Stack;
//
//class Solution {
//    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
//        List<String> constructList = new ArrayList<>();
//        for (List<String> equation : equations) {
//            constructList.addAll(equation);
//        }
//        //创建并查集
//        UnionFind unionFind = new UnionFind(constructList);
//        //遍历，将值放入并查集里面
//        for (int i = 0; i < equations.size(); i++) {
//            String node1 = equations.get(i).get(0);
//            String node2 = equations.get(i).get(1);
//            double rate = values[i];
//            unionFind.union(node1,node2,rate);
//        }
//        double[] res = new double[queries.size()];
//        for (int i = 0; i < queries.size(); i++) {
//            String node1 = queries.get(i).get(0);
//            String node2 = queries.get(i).get(1);
//            res[i] = unionFind.isConnect(node1, node2);
//        }
//        return res;
//    }
//}
//
//class UnionFind{
//
//    HashMap<String,String> fatherMap; //key：son value: father
//    HashMap<String,Double> fatherWeight;//father 是 son 的多少倍
//
//    public UnionFind(List<String> list){
//        fatherMap = new HashMap<>();
//        fatherWeight = new HashMap<>();
//        for (String s : list) {
//            fatherMap.put(s,s);
//            fatherWeight.put(s,1.0);
//        }
//    }
//
//
//    public void union(String node1,String node2,Double rate){//node1是被除数 node2为除数
//        String head1 = findHead(node1);
//        String head2 = findHead(node2);
//        if(head1!=head2){
//            //假设 node1:head1 1:10   node2:head2 1:6 node1/node2 5
//            fatherMap.put(head2,head1);
//            fatherWeight.put(head2,fatherWeight.get(node1)*rate/fatherWeight.get(node2));
//        }
//
//    }
//
//    //返回连接的两节点倍率
//    public Double isConnect(String node1,String node2){//node1是被除数 node2为除数
//        if(!fatherMap.containsKey(node1)||!fatherMap.containsKey(node2))return -1.0d;
//        String head1 = findHead(node1);
//        String head2 = findHead(node2);
//        if(head1==head2){
//            return fatherWeight.get(node2)/fatherWeight.get(node1);
//        }else {
//            return -1.0d;
//        }
//    }
//
//    public String findHead(String node){
//        Stack<String> nodeStack = new Stack<>();
//        Stack<Double> weightStack = new Stack<>();
//        while (fatherMap.get(node)!=node){
//            nodeStack.push(node);
//            weightStack.push(fatherWeight.get(node));
//            node = fatherMap.get(node);
//        }
//        double rate = 1.0;
//        while (!nodeStack.isEmpty()){
//            String pop = nodeStack.pop();
//            rate*=weightStack.pop();
//            fatherMap.put(pop,node);
//            fatherWeight.put(pop,rate);
//        }
//        return node;
//    }
//
//}